#include <stdio.h>
#include <string.h>

enum { kLeftUp, kUp, kLeft };

void LongestCommonSubsequence(const char *X, int xn, const char *Y, int yn) {
  printf("Initialize (%d, %d)...\n", xn, yn);
  int **L = new int*[yn + 1];
  for (int i = 0; i <= yn; ++i) {
    L[i] = new int[xn + 1];
    memset(L[i], 0, sizeof(int) * (xn + 1));
  }

  printf("Programming ...\n");
  for (int i = 1; i <= yn; ++i) {
    for (int j = 1; j <= xn; ++j) {
      if (X[j - 1] == Y[i - 1]) {
        L[i][j] = L[i - 1][j - 1] + 1;
      }
      else if (L[i][j - 1] > L[i - 1][j]) {
        L[i][j] = L[i][j - 1];
      }
      else {
        L[i][j] = L[i - 1][j];
      }
    }
  }

  printf("Retrieve result ...\n");
  char *result = new char[L[yn][xn]];
  int i = yn, j = xn; 
  for (int k = L[yn][xn] - 1; k >= 0; --k) {
    while (L[i][j] <= L[i - 1][j - 1]) {
      if (L[i][j] == L[i][j - 1]) --j;
      else if (L[i][j] == L[i - 1][j]) --i;
    }
    result[k] = X[j - 1];
    --i;
    --j;
  }

  printf("length: %d\n", L[yn][xn]);
  for (int i = 0; i < L[yn][xn]; ++i) {
    printf("%c", result[i]);
  }
  printf("\n");

  for (int i = 0; i <= yn; ++i) delete[] L[i];
  delete[] result;
  delete[] L;
}

int main(int argc, const char *argv[]) {
  const char *Y = "ABCBDAB"; 
  const char *X = "BDCABA";
  LongestCommonSubsequence(X, strlen(X), Y, strlen(Y));
  return 0;
}

